class Solution(object):
    def shortestPathLength(self, graph):
        n = len(graph)
        if n == 1:
            return 0
        now = {(1 << i, i) for i in range(n)}
        a_set = {(1 << i, i) for i in range(n)}
        dist = 0
        while True:
            dist += 1
            next_set = set()
            for val, node in now:
                for v in graph[node]:
                    next_val = val | (1 << v)
                    if next_val == (1 << n) - 1:
                        return dist
                    if (next_val, v) not in a_set:
                        a_set.add((next_val, v))
                        next_set.add((next_val, v))
            now = next_set


data = Solution()
# graph = [[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]]
# print(data.shortestPathLength(graph))
graph = [[1, 2, 3], [0], [0], [0]]
print(data.shortestPathLength(graph))
